ࡱ> 7  zbjbjUU "7|7| tl8888$8U96:::::X>l?0U2U2U2U2U2U2U$W YVU9?::??VUB::UBBB?f::0UB?0UBBGrQTQ:9 0N638^ArhQQdU0UvQVIZBIZQB*HYPERLINK "LZ.doc" \l "_cs320_GIF"Previous lectureHYPERLINK "Colors.doc"Next Lecture HYPERLINK "..\\320Syllabus.doc" Syllabus HYPERLINK "..\\..\\Homework\\Week7\\Week7.doc" Homework LZ legal issues PNG data is compressed using a variant of Deflate (created by Phil Katz and used in pkzip). Deflate is a variant of LZ77, which was patented in 1981-84 by Lempel, Zif, Cohen and Eastman. Deflate: variable size sliding window, sorted hash tables, Huffman encoding. PNG: No sorted hash tables and thus not subject to any patent or licensing requirements. GIF uses LZW (a variant of LZ78) which was patented in 1985. Unisys owns both the LZ77 and the LZW patents. Compuserve created GIF in 1987 without checking for patents. In 1993, Unisys became aware of the use of LZW in GIF and began negotiations with Compuserve. Compuserve had to buy a license from Unisys and announced that all developers producing software that reads or writes GIF files need to pay a royalty on each copy sold. It is legal to own, transmit and receive GIF files. A 1999 statement from Unisys: Unisys has frequently been asked whether a Unisys license is required in order to use LZW software obtained by downloading from the Internet or from other sources. The answer is simple. In all cases, a written license agreement or statement signed by an authorized Unisys representative is required from Unisys for all use, sale or distribution of any software (including so-called "freeware") and/or hardware providing LZW conversion capability (for example, downloaded software used for creating/displaying GIF images). -  HYPERLINK "http://www.unisys.com/unisys/lzw/default.asp" http://www.unisys.com/unisys/lzw/default.asp Consider a  HYPERLINK "Trivial Patent.doc" trivial patent. For more information:  HYPERLINK "http://lpf.ai.mit.edu/Patents/Gif/Gif.html" http://lpf.ai.mit.edu/Patents/Gif/Gif.html The United States LZW patent expired on June 20th, 2003. According to Unisys, the counterpart Canadian patent expires July 7, 2004, the counterpart patents in the United Kingdom, France, Germany and Italy expire June 18, 2004, and the Japanese counterpart patents expire June 20, 2004. LZW is also used by TIFF and Postscript. Adobe has licensed the technology from Unisys. By 1995. GIF had replaced PCX as the most common format for transmitting 256-color images with lossless compression. The user community was unhappy to learn that GIF is not free. JPEG quickly replaced GIF for photographic images. In order to provide a free lossless image format, Tom Boutell organized the PNG Development Group. The PNG standard was released in final form in October 1996. Patents and Copyrights There are several forms of protection for intellectual property: Trade Secrets: Dont tell anyone how you do it. Commonly used in fast moving technology. Copyright: Protects the expression of an idea, but not the idea itself. Cheap and easy. You can formally file with the Trademark Office or merely insert a line Joe Blow, 2003. Using the symbol is preferred over the word copyright since the symbol provides for international copyright. Patents: Costs about $5000 to file an application and takes years to issue. Gives the owner a monopoly on the invention. The U.S. Constitution establishes patents to promote the progress of science and the useful arts. An inventor publishes a full disclosure with the Patent Office and receives exclusive rights to the invention for 17 years. A patent may only be issued if the technique is Novel; not part of the prior art in the field Nonobvious to person having ordinary skill in the art. It is never legal to patent a mathematical formula or algorithm. Up until the early 1980s, computer software was considered an algorithm and could not be patented. When the law was changed, hundreds of inventors stepped forward to patent software techniques that had been widely used but were too trivial to publish. The Patent Office had no computer scientists on staff and issued the patents. In the May 2001 Game Developer Magazine, Chris Hecker and Casey Muratori argue Software Patents Should be Abolished. They claim that the system is broken and does not function as intended. Patent litigation costs average $1.2 million.  HYPERLINK "http://lpf.ai.mit.edu/Patents/patents.html" http://lpf.ai.mit.edu/Patents/patents.html Licensing Even with the LZW patent expired, note the following clause from the GIF89a specification (1990): The Graphics Interchange Format(c) is the copyright property of CompuServe Incorporated. Only CompuServe Incorporated is authorized to define, redefine, enhance, alter, modify or change in any way the definition of the format. CompuServe Incorporated hereby grants a limited, non-exclusive, royalty-free license for the use of the Graphics Interchange Format(sm) in computer software; computer software utilizing GIF(sm) must acknowledge ownership of the Graphics Interchange Format and its Service Mark by CompuServe Incorporated, in User and Technical Documentation. Computer software utilizing GIF, which is distributed or may be distributed without User or Technical Documentation must display to the screen or printer a message acknowledging ownership of the Graphics Interchange Format and the Service Mark by CompuServe Incorporated; in this case, the acknowledgement may be displayed in an opening screen or leading banner, or a closing screen or trailing banner. A message such as the following may be used: "The Graphics Interchange Format(c) is the Copyright property of CompuServe Incorporated. GIF(sm) is a Service Mark property of CompuServe Incorporated." For further information, please contact : CompuServe Incorporated Graphics Technology Department 5000 Arlington Center Boulevard Columbus, Ohio 43220 U. S. A. CompuServe Incorporated maintains a mailing list with all those individuals and organizations who wish to receive copies of this document when it is corrected or revised. This service is offered free of charge; please provide us with your mailing address. Users of this specification should note that the LZW compression and decompression methods described in U.S. Patent No. 4,558,302 and certain corresponding foreign patents are owned by Unisys Corporation. Software and hardware developers may be required to obtain a license under this patent in order to develop and market products using GIF LZW compression and decompression. Unisys has agreed that developers may obtain such a license on reasonable, non-discriminatory terms and conditions. Further information may be obtained from: Welch Licensing Department, Office of the General Counsel, M/S C1SW19, Unisys Corporation, Blue Bell, PA 19424. PNG (Portable Network Graphic Format) Thomas Boutell organized a PNG Development Group within days of the Unisys announcement of license fees for GIF usage. The final PNG version was released in October 1996. PNG is intended to replace GIF for lossless image compression. For lossy images, JPEG has mostly replaced GIF. PNG includes a standard toolkit for implementing readers and writers. There is a standard set of benchmark images for testing. PNG is well designed and allows for expansion. PNG has one disadvantage against GIF: Internet Explorer and Netscape do not support PNG. PNG does not do animations. On January 11, 2001, the PNG Development Group approved the MNG-1.0 (Multiple-image Network Graphics)  HYPERLINK "ftp://swrinde.nde.swri.edu/pub/mng/documents/" \l "mng" [1]. and JNG-1.0 (JPEG Network Graphics)  HYPERLINK "ftp://swrinde.nde.swri.edu/pub/mng/documents/" \l "jng" [2]. specifications, and the documents were released on January 31. MNG and JNG are additions to the PNG family. MNG is for storing and transmitting multiple-image animations and composite frames, and JNG is a MNG sub-format for encapsulating JPEG images, with alpha-channel transparency, in a format usable by MNG. GIFPNGPatent ProblemsYes (until 2004)NoCompressionLZWLZ77, filters, HuffmanByte orderLittle EndianBig EndianColor resolution256 24-bit colors256 colors up to 48 bitsColor matchingNoYesMultiple images & animationYesNoSerial data streamYesYesChecksumsNoYesTransparencyOne transparent colorFull alpha channelInterlacingBy scan lineAdam 7 on 8x8 blocks Signature IHDR Chunk PLTE Chunk (optional) IDAT Chunk IEND Chunk  Like GIF (unlike BMP, PCX), PNG is a serial data stream. You never need to seek in the file to find data at different offsets. PNG consists of several kinds of chunks, of which the most important are listed in the block above. Each chunk is a packet with the following format: typedef struct _PngChunk { DWORD DataLength; /* Size of Data field in bytes */ DWORD Type; /* Code identifying the type of chunk Equivalent to 4 ASCII characters: IHDR, PLTE, IDAT, IEND, */ BYTE Data[]; /* The actual data stored by the chunk */ DWORD Crc; /* CRC-32 value of the Type and Data fields */ } PNGCHUNK; The file must end with an IEND chunk (image trailer), which contains no data. The file must start with the PNG signature and header chunk. typedef struct _PngSignature { BYTE Signature[8]; /* Identifier (always 89504E470D0A1A0Ah) "\211PNG\r\n\032\n" Visually identification ("PNG") Detect a file transfer that alters the newline sequences ("\r\n" would become "\r", "\n" or "\n\r") Stop the file listing on MS-DOS (\032 = Control-Z) Detects file transfer CR/LF problems (the final newline) */ } PNGSIGNATURE; PngChunk /* for IHDR */ { DWORD DataLength; /* 0x08 13 */ DWORD Type; /* 0x0C: IHDR */ IHDRChunk { DWORD Width; /* 0x10 Width of image in pixels */ DWORD Height; /* 0x14 Height of image in pixels */ BYTE BitDepth; /* 0x18 Bits per pixel or per sample 1, 2, 4 or 8 for indexed color (3) 1, 2, 4, 8 or 16 for grayscale (0) 8 or 16 for other ColorTypes */ BYTE ColorType; /* 0x19 Color interpretation indicator 0 (gray-scale), 2 (truecolor), 3 (indexed color), 4 (gray-scale with alpha data), 6 (truecolor with alpha data).*/ BYTE Compression; /* 0x1A Compression type indicator Always 0 */ BYTE Filter; /* 0x1B Filter type indicator Always 0 */ BYTE Interlace; /* 0x1C Type of interlacing scheme used 0: none 1: Adam7 interlacing */ }; DWORD Crc; /* 0x1D CRC-32 on Type and Data fields */ }; Image data chunk The chunk type is  HYPERLINK "D:\\CS320\\Lectures\\GIF\\PNG.doc" \l "CS320_IDAT" IDAT. The data is the compressed image. An image may be split over more than one IDAT chunk. Image data is a bitmap scanned left to right, top to bottom. Pixels are packed into scan lines with the leftmost in the most significant bits. Scan lines are padded to end on byte boundaries. Scan lines are preceded by a  HYPERLINK \l "CS320_Filters" filter type byte.  HYPERLINK "Colors.doc" Color Representations Gamma The response of film and image scanners is generally nonlinear. Gamma measures the contrast of a photographic film. Medium contrast films have Gamma of 0.7 to 1.0. High contrast films (used to copy line originals) have gamma from 1.5 to 10. Changing the gamma value will make an image lighter or darker. The gamma for a CRT is typically 2.0 to 3.0. TV broadcast typically uses a gamma of 0.45 (NTSC) or 0.36 (PAL/SECAM). Using a gamma value less than 1 assigns more codes to the darker regions of an image. This avoids banding artifacts in the dark areas of the image and thus helps improve compression. Assume that the values for r, g and b are in the range 0 to 1. The corrected color will be (rG, gG, bG) The best value of G to use when viewing the image depends on the room lighting; 1.0 for a well-lit room to 1.5 in a dark room. Your display software does not know which value to use unless if it can read a light sensor. The effects of G are multiplicative: Gviewing = Gapplication * Gmonitor * Gfile Thus if you knew the room lighting, the G for the monitor (assume 2.5) and the G for the file, you could set the G for your application to get the right viewing colors. For more on gamma, see 13. Appendix Gamma Tutorial on page 81 of the  HYPERLINK "png-1.0-w3c.txt" PNG Standard. [demo: Starship.png on graph X viewer] Alpha Channel Suppose that you are writing a game in which your character is outside a building and looking through windows. Some of the windows have glass and some dont. There may be things in the window that you will shoot at or will shoot at you. If there is glass in the window, the first shot takes out the glass, and there is a delay until you can shoot again. You want a visual interface that lets you see whether the window has glass. One way to do this is that in a window with glass you will see both the reflection of your character and the scene inside the room. We can overlay the two images using an Alpha channel that gives the transparency. An Alpha value of 0 is totally transparent. This is useful when your sprite is not rectangular. Alpha of 2Image Bit Depth 1 is fully opaque (normal) Transparent values are in between. Interlacing Uses Adam7, which is more complicated than GIF. Progressive display is done on 8x8 pixel blocks instead of by scan line. [Miano fig 13.5] PNG optional chunks: Naming conventions for chunks [Miano Fig 13.1] [Table PNG-1] PLTE Required if Color Type in IHDR is 3 (Palette). If Color type is RGB or RGB with Alpha, then Palette is optional and provides a recommendation for which colors to use if the image is reduced to 256 colors. The data in the palette chunk are triples with one byte each for Red, Green and Blue. There may be at most 256 triples and at most 2Bit Depth triples. The PLTE chunk must come before any IDAT chunks. typedef struct _PLTEChunkEntry { BYTE Red; /* Red component (0 = black, 255 = maximum) */ BYTE Green; /* Green component (0 = black, 255 = max) */ BYTE Blue; /* Blue component (0 = black, 255 = maximum) */ } PLTECHUNKENTRY; PLTECHUNKENTRY PLTEChunk[]; cHRM For device independent color. All entries are multiplied by 100,000 typedef struct _cHRMChunkEntry { DWORD WhitePointX; /* White Point x value */ DWORD WhitePointY; /* White Point y value */ DWORD RedX; /* Red x value */ DWORD RedY; /* Red y value */ DWORD GreenX; /* Green x value */ DWORD GreenY; /* Green y value */ DWORD BlueX; /* Blue x value */ DWORD BlueY; /* Blue y value */ } CHRMCHUNKENTRY; gAMA The Image Gamma chunk stores the original gamma value of the image with respect to the original scene. The stored value is the gamma multiplied by 100,000. Note that it is "strongly" recommended by the PNG authors that decoders implement the gamma chunk. typedef struct _gAMAChunkEntry { DWORD Gamma; /* Gamma value */ } GAMACHUNKENTRY; sBIT This can be used to store the number of significant bits in the original image. This could indicate that the original image was a 12 bit image, which PNG had to store as 16 bits. Different data depending on Color Type. pHYs Specifies the absolute or relative pixel size when the image was created. If omitted, assume a square pixel. typedef struct _pHYsChunkEntry { DWORD XPixels; /* Pixels in the X direction per unit */ DWORD YPixels; /* Pixels in the Y direction per unit */ BYTE Unit; /* 0 for a ratio; 1 for unit = meters */ } PHYSCHUNKENTRY; tRNS If the alpha channel is not used, this is another way to do transparency. If the color type is 0 (gray scale) or 2 (true color), then one color is designated to mean transparent. The data contains this color as either a 2-byte integer (color type 0) or three 2-byte integers (color type 2). If the color type was 3 (palette), then the data is an array of alpha channel bytes paralleling the palette. bKGD This lets us specify a background color. hIST If a palette is used, the image histogram chunk can be used to give the approximate frequencies of the colors used. The histogram must have the same number of entries as the palette. Each histogram entry is an unsigned 2-byte integer. A value of 0 should only be used for a color that is never used. tEXt typedef struct _tEXtChunkEntry { char Keyword[]; /* Type of information stored in Text */ BYTE NullSeparator; /* NULL (0) character used a delimiter */ char Text[]; /* Textual data */ } TEXTCHUNKENTRY; Keyword is a field of character data with a length of 1 to 79 bytes. This field may contain any printable Latin-1 character except NULL. Spaces are also allowed. The defined values are: Title Author Description Copyright Creation Time Software Disclaimer Warning Source Comment [Miano table 13-8] Text is a field of character data that is the actual textual data stored in the chunk. The length of this field is determined from the value of the DataLength field in the HYPERLINK "D:\\DigiPen\\Fall2001\\CS320\\Lectures\\GIF\\PNG.doc" \l "CS320_PNG_chunk"chunk header. It will be equal to the DataLength size of Keyword 1. zTXt Same as tEXt except that the Text[] field is compressed using the same method as the image data and there is a Compression Method byte preceding the Text[]. The Compression Method must be 0. tIME The time (should be GMT, not local) when the image was last modified. typedef struct tIMEChunkEntry { WORD Year; /* Year value (such as 1996) */ BYTE Month; /* Month value (1-12) */ BYTE Day; /* Day value (1-31) */ BYTE Hour; /* Hour value (0-23) */ BYTE Minute; /* Minute value (0-59) */ BYTE Second; /* Second value (0-60) */ } TIMECHUNKENTRY;  HYPERLINK "D:\\CS320\\Lectures\\GIF\\PNG.doc" \l "CS320_IDAT" The PNG IDAT chunk [Review Huffman codes] Deflate compression Deflate uses a non-patented version of LZ77 compression. A sliding window covers the most recently processed symbols. The next code in the stream can either be a literal or a code. If it is a literal, it is added to the processed buffer and the window slides by one. A code tells us to go to the sliding window and replicate some of the data that we have already decoded. The code consists of two parts: 1) An index of where to start in the window. 2) How many symbols to copy (must be 2 or more). [Miano figure 14.1, p.217] The size of the sliding window buffer is usually 32K, but can be a smaller power of 2. This technique is fairly easy for decoding information. Encoding is more difficult, since we need to search for the longest matching string. This is done using hash tables. Huffman Coding in PNG In PNG, there are two Huffman encoded tables: 1) The literal table encodes the 256 base symbols (pixel values or palette indices) as well as codes for the size of the matching string. Code 256 marks the end of a compressed block. Codes 257-285 copy data from the sliding buffer. Each of these codes is followed by 0 to 5 extra bits. The table tells how many bytes to copy. [Miano table 14.1, p.219] 2) The distance table encodes the starting position of the string in the sliding window. There are 30 entries in this table. [Miano p.220 table 14.2 and example] PNG has two ways of doing Huffman tables: 1) Fixed: All entries in the distance table are 5 bits plus 0 to 13 extra bits. This gives a total code length of 5 to 18 bits. See table 14.2 in Miano. For the literal/length table, Codes 0 through 143 (literals) are Huffman coded in 8 bits. Codes 144 to 255 (literals) are coded in 9 bits. Code 256 (end of compressed block) is coded in 7 bits Codes 257-279 (lengths) are represented in 7 bits plus 0 to 4 extra bits. Codes 280-287 (lengths) are 8 bits plus 0, 4 or 5 extra bits. These are summaraized in table 14.8 on p.227 of Miano. When you count the extra bits, literal/lengths range from 7 to 13 bits. To figure out what the Huffman codes are, use the code length algorithm given on pp. 65-71 of Miano. The Huffman code lengths are: 24 codes of length 7 (representing length codes 256-279) 152 codes of length 8 (representing litterals 0-143 and length codes 280-287) 144 codes of length 9 (representing litterals 144-255) Huffman lengthHuffman code (binary)Huffman code (hex)Literal or Length code7000 0000 00 256 7001 01111727980011 0000 30 0 81011 1111BF14381100 0000 C0 280 81100 0111C728791 1001 0000 190 144 91 1111 11111FF255 2) Dynamic: Codes sizes are based on usage in the image. In this case, the start of the image data contains a list of the code lengths. This code length table is itself Huffman encoded, with a maximum code length of 4 bits. Putting it all together in PNG The data within the IDAT chunk has the format: typedef struct _compressedData { WORD Header; /* Reading left to right, 4 bits: Window size; must be <= 7. The window is 2^(8+Window size) 4 bits: Compression method; must be 8 2 bits: Compression method advisory 0 = fastest; 1 = fast; 2 = default; 3 = maximum 1 bit: Preset dictionary; must be 0 5 bits: Checksum to make header divisible by 31. */ BYTE[] CompressedBlock; /* Read right to left, The first 3 bits are a header: 1 bit: 1 = this is last block; 0 = more blocks follow */ 2 bits: type 0 = uncompressed data 1 = Fixed Huffman codes 2 = Dynamic Huffman codes 3 = Invalid DWORD AlderChecksum; /* Calculated on uncompressed data */ } COMPRESSEDDATA; Reading the start of an IDAT data set The start of a data set has the following format: final: 1-bit (1 => this is the last data set) compression type: 2-bits The remainder depends upon the compression type. Compression Type: Uncompressed Advance to the next byte boundary. The next two bytes is the length of the uncompressed data. The following two bytes are the ones complement of the length. [length] uncompressed bytes follow. Compression Type: Fixed Huffman Codes The Huffman encoded data bits immediately follow the type field. The data is encoded using the Huffman length codes defined in the deflate specification. Compression Type: Dynamic Huffman Codes The trick here is that the literal and distance Huffman tables are Huffman-encoded. The next values in the input stream are: number of literal codes: 5-bits + 257 number of distance codes: 5-bits + 1 number of code lengths: 4-bits + 4 The number of code lengths is 18 or less. They are stored in a permuted order: 16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15 The last entries are less likely to occur, and may be absent. If absent, their assigned code length is 0. The codes Code Lengths: 3-bits * (number of code lengths) Use the code lengths to create a Huffman table that encodes the literal/length code sizes followed by the code sizes for the distance table Make Huffman tables For either fixed or dynamic codes, use the array of code sizes to create a Huffman table for literals/lengths. Use the other array of code sizes to generate the distance table. The procedure is similar to that used for  HYPERLINK "..\\JPEG\\JPEG.DOC" \l "JPEG_Huff" JPEG Huffman tables. [Hufftabl.c] Reading the Data The number of bytes needed for each row of image data is computed from the ColorType and the Width from IHDR. Data is read by rows. The first byte in a row is the row filter type: 0 Unfiltered 1 Sub filter Difference from pixel on left 2 Up filter Difference from pixel above 3 Average filter Difference from average of pixels to left and above 4 Paeth filter Difference from value predicted by neighbors. The Paeth filter looks at the three pixels to the left, upper left, and above. The predicted value is the one of those three pixels that lies on the direction of smallest change. Specifically: Paeth( left, above, upperLeft) { horiz = abs( above upperLeft); vert = abs(left upperLeft); diag = abs( left + above 2* upperLeft); if (horiz <= vert && horiz <= diag) return left; if (vert <= diag) return above; return upperLeft; } // This function reads the pixel data for a non-interlaced image. // void PngDecoder::ReadNoninterlaced () { // Initialize the input buffers. current_row_buffer = 0 ; memset (row_buffers [0], 0, row_buffer_width) ; memset (row_buffers [1], 0, row_buffer_width) ; for (unsigned int row = 0 ; row < image_height ; ++ row) { PngFilterType filter = (PngFilterType) DecodeByte () ; for (unsigned int col = 0 ; col < row_buffer_width ; ++ col) { int value = DecodeByte () ; row_buffers [current_row_buffer][col] = value ; } FilterRow (filter) ; CopyNoninterlacedRowToImage (row) ; current_row_buffer = ! current_row_buffer ; // Switch buffers } return ; } Example On the CD ROM with Murray & vanRyper, directory GFF\SAMPLE\IMAGES\PNG has a suite of PNG test samples. See the document PNGSUITE.DOC in that directory. The file names are set up to test file readers on various aspects of the PNG format. Example file: BAS N 0G 08 . PNG Basic test, non-interlaced, color type 0 Gray scale, 08 bit color depth. 0x00 - 0x07: signature. 0x08 - 0x0B: the length of the next chunk (13 bytes) 0x0C - 0x0F: Chunk type (IHDR) 0x10 - 0x13: Width (32 pixels) 0x14 - 0x17: Height (32 lines) 0x18: Bit depth (08) 0x19: ColorType (0 gray scale) 0x1A: Compression (0) 0x1B: Filter (0) 0x1C: Interlacing (0 none) 0x1D-0x20: CRC checksum (0x56112528) 0x21 - 0x24: the length of the next chunk (4 bytes) 0x25 - 0x28: Chunk type (gAMA) 0x29 - 0x2C: Gamma * 100,000 (0x86A0 = 0.34464) 0x2D-0x30: CRC checksum (0x31e8965f) 0x31 - 0x34: the length of the next chunk (65 bytes; would need 1024 uncompressed) 0x35 - 0x38: Chunk type (IDAT) 0x39 - 0x3A: Header for compressed data (0x789C = 30876 = 996*31) Reading left to right, the header is 4 bits: Window size; 7 means 32768. 4 bits: Compression method; must be 8 2 bits: Compression method advisory 0 = fastest; 1 = fast; 2 = default; 3 = maximum 1 bit: Preset dictionary; must be 0 5 bits: Checksum to make header divisible by 31. The header is binary 0111 1000 10 0 11100 0x3B - 0x75: Compressed data block (0x63 64 60 24 ...) The first three bits [right to left] are: 01 1 (Fixed Huffman Codes; last block) 0x76 - 0x79: Alder checksum (0x50e5fe71) 0x7A - 0x7D: CRC checksum (0x35e2d859) 0x7E - 0x81: the length of the next chunk (0 bytes) 0x82 - 0x85: Chunk type (IEND) 0x86 - 0x89: CRC checksum (0xae426082) The compressed data (0x63 64 60 24 00 14...) is read as: 0x63 = 01100 01 1; bit 0 (rightmost) = 1 for last block; bits 1-2 = 01 for fixed Huffman codes Next (reading right to left) we combine the upper 5 bits from location 0x3B and the lower 3 bits from 0x3C: 00110 001 = 0x31 = 49 Using this as a Huffman code, we get a value of 1, which goes into the buffer of decoded values. This is a filter type of 1 (sub filter) In PNG, Huffman codes can be 7, 8 or 9 bits. Thus we dont know in advance whether the code is 00110 00, 00110 001, or 00110 0010. Only one of these is a valid Huffman code. Combine the upper 5 bits from location 0x3C and the lower 3 bits from 0x3D: 00110 000 = 0x30 = 48 This is the Huffman code for 0, which goes into the buffer of decoded values. This is the first pixel value, which is placed in the decoded scan line. The next decoded value is 8 bits of 00110001 = 49. This gives a value of 1 for the second pixel value. The next code is 7 bits of 0010000 = 16. When decoded from the Huffman table, it becomes code 272. Since this code has 2 extra bits, they are read from the compressed data and are 00. The base value for code 272 is 31. Plus 0 for the extra bits gives a length of 31. We next read 5 bits of distance: 00000. Index 0 into the Huffman table [Miano table 14.2] gives a distance code of 1. The current window position is 3. Thus we copy from position 2, which holds the value "1". We then increment the window position and loop 30 more times, copying from positions 3, 4, 5, .... The effect is to produce 31 copies of the value "1". This completes the row of 32 pixels with values 0, 1, 1, 1, ..., 1. On completion of the row, the row filter is invoked. The sub filter is being used. It means that each pixel after the first has been encoded as a difference. Thus the filter replaces pixel[col] += pixel[col-1] This results in a gray level ramp of 0, 1, 2, 3, ..., 31. If your PNG reader has used a gray level palette with all gray levels available you will see the ramp. If not, you will see a stair step, where each gray level is held until the next available level is reached. The next section of compressed data is (0x14 08 c8 b3 0c ...) starting at 0x40, though we have already used one bit from the value at 0x40. We start with a row filter byte. The next 8 bits decoded are 01010000 = 0x50 = 80. This index into the Huffman table gives a value 32 for the next pixel. The next value read is again 7 bits of 0010000 = 16 for code 272 and 31 repeats of the image value. For the distance, we read 5 bits of 01001. Index 9 into the Huffman distance table gives a base value of 25. This has three extra bits, which are 111. Adding 7 to the base of 25 gives a distance of 32. Since the current window position is 35, we are copying from position 3. The value here is '1'. Thus we produce another 31 copies of "1". The filter at the end of the row will again convert this to a ramp. #$%5678NOP\]^_ O P   I J K u v x jU6] OJQJ^J0JOJQJ^JjUjUjU0J5jUjvUjU0JjU jU>7^7<hfdffff$$Ifl\:,"064 la$If  z<#$B w x ~1UH & F & F01<8gR<&FGq./ b!c!!!!!!!""""V#Y#a#$/%I&'>())G-l-m------.. / ////#/$/*CJOJQJ^J0JOJQJ^JjOJQJU^J OJQJ^J 7OJQJ jU0J-qVL/r` V#V#W#X#Y#]#a#b#r#######ss~$$IflF\ ,"  D 06    4 la$If$If ########$$!$$$($)$E${{{{{{\{{{{$If~$$IflF\ ,"  D 06    4 laE$I$L$M$`$d$h$i$s$v$z${$$$${p{H{~$$IflF\ ,"  D 06    4 la$If$$$$$$$$${{{yy{$If~$$IflF\ ,"  D 06    4 la$$$$%% %!%.%/%0%H&I&b&d&&&&4`48 ^`$IfV$$Ifl T 04 la&']'''''=(>([(](((()G)|))))))) *4*>*@*|*`$a$ ^`|***+=+]++++++,P,\,,,,,,-D-G-Y--.K..^ @ ^@ ``.."/#/[/P00011R2X4466w6666899999y:::::/S/T/111111:2<2>2B2D2F2J2L2N2v2x2,4.4X4Z4h4n4p4444444445L5N555H6I6f6g6h6t6u6997<@<|<==?@ CJOJQJH*0Jj U jU 6H*]OJQJ6H*OJQJ]6] 0J56CJOJQJ\]^J)j0J56CJOJQJU\]^J/jf0J56CJOJQJU\]^J9:::::;;;J<{<|<<<<)=q=======> >=>q>>>>!?!?M?y?????#@j@@@@@@@@@AADBcBeBBB(C:C;C@CCdD@@DB:C8FGIIVIWIXIdIeIJKK;LHQHRHHHHIIIhJiJnJJJJK5K`KKKKKKQLRLiL~LMMNENvNwNNNNNN%OzOOOOiPP(Q)QCQDQQQQQQRRRRR S=StSS`SS5T}TU:UUUUUUUV$If VVVV#V)V*V,V5V8V*\<A@< Default Paragraph Font.U@. Hyperlink >*B*ph>V@> FollowedHyperlink >*B* ph&X@& Emphasis6]J^@"J Normal (Web)dd[$\$OJPJQJ^J"W@1" Strong5\,B@B, Body Text6] t !z!z!z!z!z!z!z!z! z! z! z! z! z!z!z!z!z!z!z 2H"$H)U+4:AjFIPQT}[arh t &=& 1    &97^7<#$Bwx ~ 1 U H01<8gR<&FGqVL/r`VWXY]abr  ! $ ( ) E I L M ` d h i s v z { !! !!!.!/!0!H"I"b"d""""#]#####=$>$[$]$$$$%G%|%%%%%%% &4&>&@&|&&&'=']''''''(P(\(((((()D)G)Y))*K***"+#+[+P,,,--).,/W/00w0000233333y444444444555J6{6|6666)7q77777778 8=8q8888!9M9y99999#:j:::::::::;;D<c<e<<<(=:=;=@==d>>>>?3@8@W@Y@@@ AAAcAAAAAABBB%B.B6B>BQBRBBBCCChDiDnDDDDE5E`EEEEEEQFRFiF~FGGHEHvHwHHHHH%IzIIIIiJJ(K)KCKDKKKKKKLLLLL M=MtMMM5N}NO:OOOOOOOPPPP#P)P*P,P5P8P040>0403@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@03@040C0C040iD0iD0iD0iD0iD0iD0iD0iD0iD0iD0iD0iD0iD0iD040iF0iF0iF0iF0iF0iF0iF0iF0iF0iF0iF0iF0iF040I0I0I0I0I0I0I0I0I0I0I0I0I(0I0L0L0L00L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L0L(0000000000000000000000000000000(0000(00(0000000000(00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000CMP<qV##E$$$&|*.:!?dDHNSV?V|VVWk[bfjq z?ABDEFGHIJKLNOQRSTUVWXYZ[\]^ z@$57O\^OJu.bl)))* ++#+=+S+H0g0t0CWCdCE>fb"Uh ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(^`o()^`.pLp^p`L.@ @ ^@ `.^`.L^`L.^`.^`.PLP^P`L.h ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(h ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(*)>>2A/P*                  7^XY]abr  ! $ ( ) E I L M ` d h i s v z { !! !!!.!/!OOOOPPPP#P)P*P,P5P8P?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefgijklmnopqrstuvwxyz{|}~Root Entry FDData `1TablehIZWordDocument"SummaryInformation(DocumentSummaryInformation8CompObjjObjectPoolDD  FMicrosoft Word Document MSWordDocWord.Document.89q